void Sweap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    int keyi = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        Sweap(&a[left], &a[right]);
    }
    Sweap(&a[keyi], &a[left]);
    keyi = left;
    return keyi;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int key=a[left];
    int hole = left;
    while (left < right)
    {
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;

        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi]&&++prev!=cur)
        {
            Sweap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    Sweap(&a[keyi], &a[prev]);
    keyi = prev;
    return keyi;
}
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
    
    int keyi = PartSort3(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);

}


int main()
{
    int a[] = { 9,8,7,5,2,7,10,8,7,80,1 };
    QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}